﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace YouWei.Console
{
    public abstract class BaseSearchEx
    {
        #region Class
        #endregion

        #region 私有变量
        protected string[] _keywords;
        protected Int32[][] _guides;
        protected Int32[] _key;
        protected Int32[] _next;
        protected Int32[] _check;
        protected Int32[] _dict;
        #endregion

        #region 设置关键字
        /// <summary>
        /// 设置关键字
        /// </summary>
        /// <param name="keywords">关键字列表</param>
        public virtual void SetKeywords(ICollection<string> keywords)
        {
            _keywords = keywords.ToArray();
            var length = CreateDict(keywords);
            var root = new TrieNodeEx();

            for (Int32 i = 0; i < _keywords.Length; i++)
            {
                var p = _keywords[i];
                var nd = root;
                for (Int32 j = 0; j < p.Length; j++)
                {
                    nd = nd.Add((char)_dict[p[j]]);
                }
                nd.SetResults(i);
            }

            List<TrieNodeEx> nodes = new List<TrieNodeEx>();
            // Find failure functions
            foreach (TrieNodeEx nd in root.m_values.Values)
            {
                nd.Failure = root;
                foreach (TrieNodeEx trans in nd.m_values.Values) nodes.Add(trans);
            }
            // other nodes - using BFS
            while (nodes.Count != 0)
            {
                List<TrieNodeEx> newNodes = new List<TrieNodeEx>();

                foreach (TrieNodeEx nd in nodes)
                {
                    TrieNodeEx r = nd.Parent.Failure;
                    char c = nd.Char;

                    while (r != null && !r.m_values.ContainsKey(c)) r = r.Failure;
                    if (r == null)
                        nd.Failure = root;
                    else
                    {
                        nd.Failure = r.m_values[c];
                        foreach (var result in nd.Failure.Results)
                            nd.SetResults(result);
                    }

                    // add child nodes to BFS list 
                    foreach (TrieNodeEx child in nd.m_values.Values)
                        newNodes.Add(child);
                }
                nodes = newNodes;
            }
            root.Failure = root;
            foreach (var item in root.m_values.Values)
            {
                TryLinks(item);
            }
            build(root, length);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="node"></param>
        private void TryLinks(TrieNodeEx node)
        {
            node.Merge(node.Failure);
            foreach (var item in node.m_values.Values)
            {
                TryLinks(item);
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="root"></param>
        /// <param name="length"></param>
        private void build(TrieNodeEx root, Int32 length)
        {
            TrieNodeEx[] has = new TrieNodeEx[0x00FFFFFF];
            length = root.Rank(has) + length + 1;
            _key = new Int32[length];
            _next = new Int32[length];
            _check = new Int32[length];
            List<Int32[]> guides = new List<Int32[]>();
            guides.Add(new Int32[] { 0 });
            for (Int32 i = 0; i < length; i++)
            {
                var item = has[i];
                if (item == null) continue;
                _key[i] = item.Char;
                _next[i] = item.Next;
                if (item.End)
                {
                    _check[i] = guides.Count;
                    guides.Add(item.Results.ToArray());
                }
            }
            _guides = guides.ToArray();
        }

        #endregion

        #region 生成映射字典

        private Int32 CreateDict(ICollection<string> keywords)
        {
            Dictionary<char, Int32> dictionary = new Dictionary<char, Int32>();

            foreach (var keyword in keywords)
            {
                for (Int32 i = 0; i < keyword.Length; i++)
                {
                    var item = keyword[i];
                    if (dictionary.ContainsKey(item))
                    {
                        if (i > 0)
                            dictionary[item] += 2;
                    }
                    else
                    {
                        dictionary[item] = i > 0 ? 2 : 1;
                    }
                }
            }
            var list = dictionary.OrderByDescending(q => q.Value).Select(q => q.Key).ToList();
            var list2 = new List<char>();
            var sh = false;
            foreach (var item in list)
            {
                if (sh)
                {
                    list2.Add(item);
                }
                else
                {
                    list2.Insert(0, item);
                }
                sh = !sh;
            }
            _dict = new Int32[char.MaxValue + 1];
            for (Int32 i = 0; i < list2.Count; i++)
            {
                _dict[list2[i]] = i + 1;
            }
            return dictionary.Count;
        }
        #endregion
    }
}
